package medium;

import data.ListNode;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/8/9 19:54
 */
public class No19_删除链表的倒数第N个结点 {
    public static void main(String[] args) {
        Solution19 solution19 = new Solution19();
        ListNode head = new ListNode(1);
        head.add(2);
        head.add(3);
        head.add(4);
        head.add(5);
        
        ListNode res = solution19.removeNthFromEnd(head, 6);
        System.out.println();

    }
}

class Solution19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //快慢指针??
        ListNode headCp = new ListNode(-1);
        headCp.next = head;
        //快慢指针 red:慢 green:快
        ListNode red = headCp;
        ListNode green = headCp;
        //快指针行:n个
        int check = 0;
        while (check != n && green != null && green.next != null) {
            check++;
            green = green.next;
        }
        
        //判断长度问题
        if (n > check || n < 0) {
            return head;
        }
        
        //这时候:red,跟green 间隔 n个位置
        //继续:红绿一起
        while (green != null && green.next != null) {
            red = red.next;
            green = green.next;
        }
        //出来之后,green指向最后,此时,red位置就是要删除的元素的前一个节点
        red.next = red.next.next;
        return headCp.next;
    }
}


    
    //public ListNode removeNthFromEnd(ListNode head, int n) {
    //    //通过空间换时间的方式实现一次遍历
    //    //(路径编号:队长所在位:0)
    //    Map<Integer, ListNode> map = new HashMap<>();
    //    ListNode headCp = new ListNode(-1);
    //    headCp.next = head;
    //    //队长扔map
    //    map.put(0, headCp);
    //    //多个小兵
    //    ListNode dealHead = headCp;
    //
    //    int length = 0;
    //    while (dealHead != null && dealHead.next != null) {
    //        length++;
    //        dealHead = dealHead.next;
    //        map.put(length, dealHead);
    //    }
    //    if (n > length || n < 0) {
    //        return head;
    //    }
    //    
    //    //获取倒数n+1
    //    int check = length - n;
    //    //获取删除元素的前一个
    //    ListNode delete = map.get(check);
    //    
    //    //路径干掉
    //    delete.next = delete.next.next;
    //    return headCp.next;
    //
    //}



    //public ListNode removeNthFromEnd(ListNode head, int n) {
    //    //获取长度,获取元素,删除元素
    //    
    //    //队长位置
    //    ListNode headCp = new ListNode(-1);
    //    headCp.next = head;
    //    //小兵和队长都处于头位置
    //    ListNode dealHead = headCp;
    //    int length = 0;
    //    //小兵冲锋
    //    while (dealHead != null && dealHead.next != null) {
    //        //获取长度
    //        length++;
    //        dealHead = dealHead.next;
    //    }
    //
    //    if (n > length || n < 0) {
    //        return head;
    //    }
    //    
    //    //获取元素,哪个元素???
    //    //获取倒数第n+1个元素
    //    //队长叫回小兵
    //    dealHead = headCp;
    //    //接下来要到的倒数第n+1元素的位置
    //    int check = 0;
    //    while (check != length - n && dealHead != null && dealHead.next != null) {
    //        check++;
    //        dealHead = dealHead.next;
    //    }
    //    //开始删除
    //    //路径干掉:干掉了倒数第n个元素
    //    dealHead.next = dealHead.next.next;
    //    return headCp.next;
    //}
